import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PathSum {
    /**
     * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     * 叶子节点 是指没有子节点的节点。
     * 链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
     * @param root
     * @param target
     * @return
     */
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {

        if (root==null)
            return ans;
        dfs(root,target);
        return ans;
    }

    public void dfs(TreeNode treeNode,int target){
        if (treeNode==null)
            return;
        path.add(treeNode.val);
        target = target-treeNode.val;
        if (treeNode.left==null&&treeNode.right==null&&target==0){
            ans.add(new ArrayList<>(path));
        }
        dfs(treeNode.left,target);
        dfs(treeNode.right,target);
        path.remove(path.size()-1);
    }


    public static void main(String[] args) {

    }

}
